// An implementation of a disjoint set data structure that answers
// two questions efficiently
//      Are two items in the same set
//      Can we merge the two different sets
//
// This is the efficient way to implement the Randomized Kruskal's
// Algorithm for generating a maze

#ifndef DISJOINT_TREE_H
#define DISJOINT_TREE_H

#include <string.h>
using namespace std;

template <typename T>
class DisjointSet {
  private:
    DisjointSet * parent; // Contains a pointer to another DT
    T data; // Contains the data in this DT
    int rank; // Contains approximate number of nodes levels in
              // current set
  public:
    /* Initializer for a Disjoint Set
     *
     * Parameter - T Contents - the contents that this DT will contain
     */
    DisjointSet(T contents); 
    /* Destructor for a Disjoint Set
     */
    ~DisjointSet();
    /* Checks if two DT nodes are in the same tree
     *
     * Returns bool of whether or not they are in the same set
     */
    bool sameSet(DisjointSet * other);
    /* Joins the sets of two DT nodes together, or returns if they
     * are already in the same set.
     *
     * Returns 0 if union occured and 1 otherwise
     */
    int Union(DisjointSet * other);
    /* Finds the node at the root of the DT that contains the node of
     * interest. This is used to compare the sets
     *
     * Returns a pointer to the root node of the DT that contains this node
     */
    DisjointSet<T> * Find();
    
    /* Get the data contained in a DT
     *
     * Returns T data, the data contained
     */

    T getData();

    /*  Print out the tree for debugging purposes
     *
     *  Returns - nothing
     */

    void DebugPrint();
};

#include "disjoint.inl"

#endif


